[题解]ARC103

2020-11-01

A /\/\/\/

题意

给定偶数长度的序列 $\{a_n\}$，每次可以选择一个数替换掉一个位置，问最少操作多少次使得对于所有 $i$，$a_i=a_{i+2}\neq a_{i+1}$。$n\le 10^5$。

题解

即让数列满足有且只有两种数字，$a_1$ 和 $a_2$。所以我们只需要确定这两个值取什么比较好。我们将原数列拆分成两个数列，奇项和偶项。我们对这两个数列分别求出哪个元素最多或次多，然后枚举4种情况，让 $a_1\neq a_2$ 即可。

#include<bits/stdc++.h>
#define rep(i,a,b) for(register int i=(a);i<=(b);i++)
using namespace std;
const int N=1e5+9;

int n,a[N],c[N][2],mx[2][2],gp[2];

int main() {
	scanf("%d",&n);
	rep(i,1,n) scanf("%d",&a[i]), c[a[i]][i%2]++;
	rep(g,0,1) rep(i,1,100000) {
		if(c[i][g]>c[mx[g][1]][g]) mx[g][1]=i;
		if(c[mx[g][1]][g]>c[mx[g][0]][g]) swap(mx[g][1],mx[g][0]);
	}
	rep(g,0,1) gp[g]=c[mx[g][0]][g]-c[mx[g][1]][g];
	if(mx[0][0]!=mx[1][0]) printf("%d\n",n-c[mx[0][0]][0]-c[mx[1][0]][1]);
	else printf("%d\n",n-c[mx[0][0]][0]-c[mx[1][0]][1]+min(gp[0],gp[1]));
	return 0;
}

B Robot Arms

题意

给定 $n$ 组坐标。构造长度为 $m$ 的序列 $c_i$ 和 $n$ 组路径方向，满足对于每一组坐标

对于每个坐标，从原点出发，走 $m$ 步。每一步可以沿着这一组路径方向走 $c_i$。
走完以后刚好走到这组坐标。
$m\le 40, c_i\le 10^{12}$。

$1\le n\le 1000$。

题解

比较明显，$m$ 在 $\log$ 级别，又看到凑整数拆分可以想到倍增的数列 $1,2,4,8…$。所以我们可以发现。然后分奇偶讨论。偶数的话还需要再加一个 $1$。

看一下什么时候无解。无解情况即出现了 $x_i+y_i$ 奇偶性和其他不同的情况。

然后看怎么构造路径。可以贪心构造解。每次往距离 $(x,y)$ 最近的点走即可。

#include<bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(register int i=(a);i<=(b);i++)
#define per(i,a,b) for(register int i=(a);i>=(b);i--)
using namespace std;
const int N=1e6+9;

int n,x[N],y[N],t=-1,c[N];
char dir[N];

signed main() {
	scanf("%lld",&n);
	rep(i,1,n) {
		scanf("%lld%lld",&x[i],&y[i]);
		if(t==-1) t=(x[i]+y[i])%2;
		else if(t!=(abs(x[i]+y[i])&1)) return puts("-1"), 0;
	}
	printf("%lld\n",32-t);
	if(t) {rep(i,0,30) printf("%lld",c[i+1]=(1<<i)), putchar(i==30 ? '\n' : ' ');}
	else {
		printf("%lld ",c[1]=1);
		rep(i,0,30) printf("%lld",c[i+2]=(1<<i)), putchar(i==30 ? '\n' : ' ');
	}
	rep(i,1,n) {
		int ux=0, uy=0;
		per(j,32-t,1) {
			int vx=x[i]-ux, vy=y[i]-uy;
			if(abs(vx)>abs(vy)&&vx>0) ux+=c[j], dir[j]='R';
			else if(abs(vx)<=abs(vy)&&vy>0) uy+=c[j], dir[j]='U';
			else if(abs(vx)>abs(vy)&&vx<=0) ux-=c[j], dir[j]='L';
			else uy-=c[j], dir[j]='D';
		}
		rep(j,1,32-t) putchar(dir[j]); puts("");
	}
	return 0;
}

C Tr/ee

题意

给定长 $1$ 的01序列 $s$，构造一棵 $n$ 个节点的树，满足若 $s_i$ 为 $1$ 则一定存在割掉一条边后大小为 $i$ 的连通块，否则一定不存在。

$n\le 10^5$。

题解

是否有解很好判断（自己独立想出来了），但是构造需要熟悉树的结构。

有解情况满足：$s_0=0, s_1=1, s_i=s_{n-i}$。

我们可以用一种类似于往链上套菊花的方法去构造树。假设有 $k$ 个 1，位置 $id_1…id_k$。于是我们取一条 $k+1$ 的链，然后链上的第 $i$ 个点挂上 $id_i-id_{i-1}-1$ 个点的菊花。

#include<bits/stdc++.h>
#define rep(i,a,b) for(register int i=(a);i<=(b);i++)
using namespace std;
const int N=1e5+9;

char s[N];
int n,k,id[N];

bool check() {
	if(s[1]=='0'||s[n]=='1') return 0;
	rep(i,1,n/2) if(s[i]!=s[n-i]) return 0;
	return 1;
}

int main() {
	scanf("%s",s+1), n=strlen(s+1);
	if(!check()) return puts("-1"), 0;
	rep(i,1,n) if(s[i]=='1') id[++k]=i;
	int node=k+1; 
	rep(i,1,k) {
		printf("%d %d\n",i,i+1);
		rep(j,1,id[i]-id[i-1]-1) printf("%d %d\n",i,++node);
	}
	return 0;
}